// 思路：1. 根据数组中整数元素计算区间确定计数数组的长度，然后把整数值映射到计数数组的索引上
// 2. 统计元素的个数
// 3. 根据计数数组回填
// 时间复杂度：On+k
// 空间复杂度：Ok
// 稳定性：稳定
// 场景： 非负整数排序，大数据量，数据分布均匀，辅助排序
function countingSort(arr) {
    let maxVal = Math.max(...arr)
    let minVal = Math.min(...arr)
    let countArr = new Array(maxVal - minVal + 1).fill(0)
    // 计算每个元素出现的次数
    for (let i = 0; i < arr.length; i++) {
        countArr[arr[i] - minVal] += 1        
    }
    // 计算元素的总数
    for (let i = 1; i < countArr.length; i++) {
        countArr[i] += countArr[i-1]        
    }

    // 回填
    let result = new Array(arr.length)
    for (let i = 0; i < arr.length; i++) {
        result[countArr[arr[i] - minVal] - 1] = arr[i]
        countArr[arr[i] - minVal]--
    }
    return result
}

let arr = [1, 2, 7, 26, 25, 7, 19, 17, 1, 90, 3, 36]
console.log(countingSort(arr))